#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node {
	int value;
	struct node *left;
	struct node *right;
};

#define NUM 8 

void insert(struct node *root, struct node *new)
{
	if (root->value > new->value) {
		if (!root->left)
			root->left = new;
		else 
			insert(root->left, new);
	} else {
		if (!root->right)
			root->right = new;
		else 
			insert(root->right, new);
	}
}

void mid_print(struct node *node)
{
	if (node->left)
		mid_print(node->left);
	printf("%d\t", node->value);
	if (node->right)
		mid_print(node->right);
}

struct node *search(struct node *root, int value, struct node **parent)
{
	struct node *pos = root;
	while (pos) {
		if (pos->value > value) {
			*parent = pos;
			pos = pos->left;
		} else if (pos->value < value) {
			*parent = pos;
			pos = pos->right;
		} else {
			break;
		}
	}
	return pos;
}

void delete(struct node *root, int value)
{
	struct node *del_node = NULL, *parent = NULL;

	del_node = search(root, value, &parent);
	if (NULL == del_node)
		return;
	if (del_node == root)
		root = del_node;
	else 
		parent->left = del_node->left;

	insert(root, del_node->right);
	free(del_node);
}

void free_all(struct node *node)
{
	if (node->left)
		free_all(node->left);
	if (node->right)
		free_all(node->right);
	free(node);
}

int main(void) {
	int data[NUM] = {1, 3, 2, 9, 7, 8, 4, 6};
	int i = 0;
	struct node *root = NULL, *node = NULL;

	for (i = 0; i < NUM; i++) {
		node = (struct node *)malloc(sizeof(struct node));
		if (!node) {
			// error handle
			;
		}
		memset(node, 0, sizeof(struct node));
		node->value = data[i];

		if (i == 0) 
			root = node;
		else 
			insert(root, node);
	}

	mid_print(root);
	printf("\n");

	delete(root, 7);
	mid_print(root);
	printf("\n");

	free_all(root);

	return 0;
}

